import java.util.List;
import java.util.LinkedList;

class Solution {
    static List<List<Integer>> ret;
    static List<Integer> path;

    public static List<List<Integer>> subsets(int[] nums) {
        ret = new LinkedList<>();
        path = new LinkedList<>();

        // 遍历决策树
        dfs(nums, 0);
        return ret;
    }

    // 针对 数组的第几个元素 做出选择
    private static void dfs2(int[] nums, int i) {
        // 当遍历到叶子结点时，即是最终结果
        if (i == nums.length) {
            // 重新new一个对象，防止回溯时被修改
            ret.add(new LinkedList<>(path));
            return;
        }

        // 由于这里是一棵二叉树，因此我们可以使用遍历二叉树的方式
        // 左子树
        dfs(nums, i+1);
        // 根结点
        path.add(nums[i]);
        // 右子树
        dfs(nums, i+1);
        // 回溯的过程中，将修改后的结果，还原
        path.remove(path.size()-1);
    }

    private static void dfs(int[] nums, int i) {
        // 每一个结点都是符合要求的子集
        ret.add(new LinkedList<>(path));

        // 从i位置开始，遍历往后的数据即可
        for (int j = i; j < nums.length; j++) {
            path.add(nums[j]);
            dfs(nums, j+1);
            // 回溯的过程，还原现场
            path.remove(path.size()-1);
        }
    }

    public static void main(String[] args) {
        subsets(new int[]{1,2,3});

        System.out.println("sfsda");
    }
}